from typing import *
from collections import deque


class Solution:

    def openLock(self, deadends: List[str], target: str) -> int:
        if '0000' in deadends:
            return -1
        b = set([tuple(map(int, v)) for v in deadends])
        q = deque([(0, [0, 0, 0, 0])])
        v = set([(0, 0, 0, 0)])
        t = [int(v) for v in target]
        while q:
            cnt, code = q.popleft()
            if code == t:
                return cnt
            for i in range(4):
                c = code[i]
                code[i] = (c + 1) % 10
                if tuple(code) not in v and tuple(code) not in b:
                    v.add(tuple(code))
                    q.append((cnt + 1, code.copy()))
                code[i] = (c + 9) % 10
                if tuple(code) not in v and tuple(code) not in b:
                    v.add(tuple(code))
                    q.append((cnt + 1, code.copy()))
                code[i] = c
        return -1


so = Solution()
print(
    so.openLock(deadends=["0201", "0101", "0102", "1212", "2002"],
                target="0202"))
